Secret keys used in encryption systems are generally generated by use of random numbers. Random numbers are largely classified into pseudo random numbers and physical random numbers (i.e., true random numbers) according to the method of generation. Pseudo random numbers are a part of a numerical sequence generated by deterministic calculation. An initial value referred to as a seed is fed into a pseudo random number generation algorithm to generate a pseudo random number sequence. With the knowledge of the generation method (i.e., pseudo random number generation algorithm) and the seed, theoretically, one can predict pseudo random numbers. With the knowledge of the internal initial value (i.e., seed), it is possible to calculate pseudo random numbers in advance. Because of this, using random numbers alone as the mechanism to generate secret keys may undermine security.
Physical numbers are generated by utilizing a physical phenomenon that is intrinsically random such as thermal noise within a device. Such random numbers are not repeatable, and no one can predict. Such a secret key generation method ensures tight security.
A physical random number generator is susceptible to environmental variation such as changes in temperature and voltage. Randomness of generated random numbers is known to be degradable depending on the environment. Random numbers having low-degree randomness carries a risk of being easily predicted, and, thus, the use of such random numbers in their original state had better be avoided in secret key generation. It is preferable to input random numbers into a circuit for correcting the randomness of physical random numbers before using them in applications such as secret key generation that require security.
An entropy compressing apparatus may be used as a circuit for correcting the randomness of physical random numbers. An entropy compressing apparatus may compress the entropy of a random number sequence having a length of 10 bits in which the entropy of each single bit is 0.5 bit, for example, thereby generating a random number series having a length of 5 bits in which the entropy of each single bit is 1.0 bit. In this example, entropy compression serves to increase entropy per bit from 0.5 bit to 1.0 bit. In this example of entropy compression, the per-bit entropy of output random numbers is greater than the per-bit entropy of input random numbers. However, the total entropy of the output random numbers does not exceed the total entropy of the input random numbers. In the case of the highest efficiency, the total entropy of output random numbers of an entropy compressing apparatus is equal to the total entropy of input random numbers.
In the following, an example will be considered in which an N-bit random number sequence generated by a physical random number generator is input into an entropy compressing apparatus for entropy compression, and an L-bit random number sequence is output from the entropy compressing apparatus. A minimum entropy M of the random number sequence output from the physical random number generator is estimated. Based on the value of the minimum entropy M, a length N of a random number sequence input into the entropy compressing apparatus is determined. The lower the minimum entropy M, the longer the bit length of a random number sequence input into the entropy compressing apparatus (i.e., the larger the value of N) is required in order to generate a physical random number sequence having a bit length of L and having a desired entropy amount. N, i.e., the bit length of the input applied to the entropy compressing apparatus, is determined by the following formula, based on the minimum per-bit entropy M estimated at the time of manufacture, a per-bit entropy E required for a physical random number sequence produced as a final output, and the output length L.N=EL/M  (1)
The input length N of the entropy compressing apparatus is a fixed value that is calculated at the time of manufacture. In the case that the entropy of a random number sequence generated by the physical random number generator exceeds the estimated minimum entropy M at the time of actual operations, the random number sequence input into the entropy compressing apparatus does not have to be N bits in length. Despite this fact, an N-bit random number sequence is always used as an input. Since the processing time of the entropy compressing apparatus is proportional to the input length N, the situations as described above means that a needless processing time is consumed in order to perform an unnecessary process.
Moreover, at the time of actual operations, the entropy of a random number sequence output from the physical random number generator may sometimes drop below the estimated minimum entropy M. Such a phenomenon may occur due to malicious cooling performed by using a cooling spray or the like against the physical random number generator, or may occur due to aging deterioration. In such a case, the entropy compressing apparatus cannot generate an output random number sequence having a bit length L and having a required entropy value based on the N-bit input random number sequence.
It is preferable to institute some control procedure to allow proper entropy compression to be performed even when the entropy of a random number sequence actually output from the physical random number generator has fluctuation. In so doing, a circuit size relating to the added control procedure had better be as small as possible because random numbers generated by entropy compression may sometimes be used in small, portable smart cards, encrypted communication for portable phones, or authentication of digital certificates. Further, the added control procedure for allowing proper entropy compression preferably do not lower the speed of processing for generating entropy-compressed random numbers to the extent that is possible.    [Patent Document 1] Japanese Patent No. 4527127    [Patent Document 2] Japanese Laid-open Patent Publication No. 8-512438    [Patent Document 3] Japanese National Publication of International Patent Application No. 2011-530719